/**
尾插法建立单链表:
初始化单链表
设置变量length 记录链表长度
While 循环{每次取一个数据元素e;Listinsert (L, length+1, e)插到尾部;length++;
头插法建立单链表:
就是每次都在头结点后面插入元素
 */
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

typedef int DataType;
typedef struct Node
{
    DataType data;
    struct Node *next;
} Node, *LinkList;

// 尾插法建立单链表
LinkList List_TailInsert(LinkList *L)
{
    DataType x;
    *L = (LinkList)malloc(sizeof(Node)); // 建立头结点
    Node *s, *r = *L;                    // r为表尾指针
    scanf("%d", &x);                     // 输入节点的值
    while (x != 9999)
    {
        s = (Node *)malloc(sizeof(Node));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d", &x); // 输入节点的值
    }
    r->next = NULL;
    return *L;
}
// 头插法建立单链表
LinkList List_HeadInsert(LinkList *L)
{
    Node *s;
    DataType x;
    *L = (Node *)malloc(sizeof(Node)); // 创建头结点
    (*L)->next = NULL;                 // 初始化头结点
    scanf("%d", &x);
    while (x != 9999)
    {
        s = (Node *)malloc(sizeof(Node)); // 创建新结点
        s->data = x;
        s->next = (*L)->next;
        (*L)->next = s;
        scanf("%d", &x);
    }
    return *L;
}
// 链表逆置
LinkList ReverseList(LinkList L)
{
    // 取出每个节点的值用头插法插入链表
    if (L == NULL)
    {
        return NULL;
    }
    Node *s, *p = L;
    LinkList newL;
    newL = (Node *)malloc(sizeof(Node)); // 创建头结点
    newL->next = NULL;
    while (p != NULL)
    {
        // printf("%d ", p->data);
        //=======================
        s = (Node *)malloc(sizeof(Node)); // 创建新结点
        s->data = p->data;
        s->next = newL->next;
        newL->next = s;
        //=======================
        p = p->next;
    }
    return newL;
}
// 打印链表
void printList(LinkList L)
{
    Node *p = L;
    while (p != NULL)
    {
        printf("%d -> ", p->data);

        p = p->next;
    }
    printf("NULL\n");
}
int main()
{
    LinkList L1, L2;
    List_TailInsert(&L1);
    printList(L1->next);
    // List_HeadInsert(&L2);
    // printList(L2->next);

    printf("链表逆置\n");
    L2 =  ReverseList(L1->next);
    printList(L2->next);
    return 0;
}